[LeetCode-319]灯泡开关

原题链接

题目描述

给出n个灯泡(初始全部熄灭)并且操作n次, 第i次把所有是i的倍数处的灯泡的开关状态取反. 求n次操作后亮着的灯泡数目.

思路

• 考虑某一个灯泡i在n次操作中被操作的次数, 可以发现该灯泡会被它的所有因子操作. 比如8会在第1、2、4、8次操作时操作.
• 若一个灯泡被操作k次, 那么该灯泡一定有k个不同的因子. 且该灯泡最后的状态唯一取决于k的奇偶. 即若k为偶数则灭, k为奇数则亮.
• 问题转化成求$1 - N$中含有奇数个不同因子的数的个数. 考虑到所有因子都是成对出现的, 若数K有奇数个不同的因子, 那么某个因子一定出现两次, 该因子一定是$\sqrt K$, 即K必为完全平方数.
• 最后问题转化成求$1 - N$中完全平方数的个数.

Code

using LL = long long;
class Solution {
public:
    int bulbSwitch(int n) {
        if (n == 0)
            return 0;
        int cnt = 0;
        for (LL i = 1; i * i <= n; i ++ )
            cnt ++ ;
        return cnt;
    }
};

复杂度分析

1. 时间复杂度$O(\sqrt N)$
2. 空间复杂度$O(1)$

---

欢迎讨论指正